package com.leetcode.dynamic_programming;

/**
 * @author Dennis Li
 * @date 2020/7/20 8:43
 */
public class MinDistance_72 {
    public int minDistance(String word1, String word2) {
        int high = word1.length(), width = word2.length();
        // 注意给dp的初始大小要+1，因为要考虑
        int[][] dp = new int[high + 1][width + 1];
        dp[0][0] = 0;
        // 初始化 -- 当为j = 0时，只需要删除
        for (int i = 1; i <= high; i++) dp[i][0] = i;
        // 当 i = 0时，只需要添加
        for (int i = 1; i <= width; i++) dp[0][i] = i;

        for (int i = 1; i < high; i++) {
            for (int j = 1; j < width; j++) {
                if (word1.charAt(i - 1) != word2.charAt(j - 1))
                    // 根据转移方程定义，当出现不同时，取三种修改方式的最小值+1
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
                else
                    // 如果不需要修改，那么就赋前面的值
                    dp[i][j] = dp[i - 1][j - 1];
            }
        }
        return dp[high][width];
    }

    public int minDistance_better(String word1, String word2) {
        int high = word1.length(), width = word2.length();
        // 注意给dp的初始大小要+1，因为要考虑
        int[] dp = new int[width + 1];
        for (int i = 0; i <= width; i++) dp[i] = i;
        for (int i = 1; i <= high; i++) {
            int temp = dp[0];
            // 向下移动一个矩阵过后，dp[0] 赋值为最初的 i，再通过一个temp记录之前的值
            dp[0] = i;
            for (int j = 1; j <= width; j++) {
                // 这里的pre代表的就是i-1，j-1的值
                // 通过pre与temp两个变量实现对值的记录
                int pre = temp;
                temp = dp[j];
                if (word1.charAt(i - 1) != word2.charAt(j - 1)) {
                    dp[j] = Math.min(dp[j], Math.min(dp[j - 1], pre)) + 1;
                } else
                    dp[j] = pre;
            }
        }
        return dp[width];
    }

}
